
public class Main2 {
    public static void main(String[] args) {
        System.out.println(JumpFloor4(6,9));
    }


    // 青蛙跳台阶 递归
    public static int JumpFloor1(int target){

        if(target == 0) return 0;
        if(target == 1) return 1;
        if(target == 2) return 2;
        return JumpFloor1(target-1) + JumpFloor1(target-2);
    }

    // 迭代
    public static int JumpFloor2(int target){

        if(target == 0) return 0;
        if(target == 1) return 1;
        if(target == 2) return 2;

        int pre1 = 1;
        int pre2 = 2;

        for (int i = 3; i <= target ; i++) {
            int cur = pre1 + pre2;
            pre1 = pre2;
            pre2 = cur;
        }
        return pre2;
    }


    // 一次可以跳1、2、...n级台阶
    /*
     * f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(1) + f(0)
     * f(n-1) = f(n-2) + f(n-3) + ... + f(1) + f(0)
     * ===> f(n) = f(n-1)+f(n-1) = 2*f(n-1)
     * */
    public static int JumpFloor3(int target){
        if(target == 0) return 0;
        if(target == 1) return 1;
        if(target == 2) return 2;
        return 2*JumpFloor3(target-1);
    }

    //case4: 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上m级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
    public static int JumpFloor4(int target,int m){
        if(m < target){
            // f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-m)
            // f(n-1) = f(n-2) + f(n-3) + ... + f(n-m) + f(n-m-1)
            // 化简得：f(n) = 2f(n-1) - f(n-m-1)
            return 2*JumpFloor4(target-1,m)-JumpFloor4(target-m-1,m);
        }else{
            // 回归到情况3
            if(target <= 1){
                return 1;
            }else{
                return 2*JumpFloor4(target-1,m);
            }
        }
    }



}
